/// @tags: SegmentTree
#include <cctype>
#include <cstdio>
#include <iostream>
#include <set>

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

constexpr int maxn = 3e5 + 3, segn = maxn * 4;

int n, m;
int a[maxn];

template <typename T>
inline T& read(T& x) {
  x = 0;
  bool f = false;
  int ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

struct Node {
  LL sum, tag;
} tr[segn];

inline void pushUp(int x) { tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum; }

inline void applyTag(int x, int l, int r, int val) {
  tr[x].tag += val;
  tr[x].sum += (LL)val * (r - l + 1);
}

inline void pushDown(int x, int l, int r) {
  if (tr[x].tag) {
    int mid = (l + r) >> 1;
    applyTag(x << 1, l, mid, tr[x].tag);
    applyTag(x << 1 | 1, mid + 1, r, tr[x].tag);
    tr[x].tag = 0;
  }
}

void modify(int x, int l, int r, int L, int R, int val) {
  if (L <= l && r <= R) return applyTag(x, l, r, val);
  pushDown(x, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) modify(x << 1, l, mid, L, R, val);
  if (mid < R) modify(x << 1 | 1, mid + 1, r, L, R, val);
  pushUp(x);
}

LL query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return tr[x].sum;
  pushDown(x, l, r);
  int mid = (l + r) >> 1;
  LL res = 0;
  if (L <= mid) res += query(x << 1, l, mid, L, R);
  if (mid < R) res += query(x << 1 | 1, mid + 1, r, L, R);
  return res;
}

inline LL query(int k) { return query(1, 1, n, 1, k); }

std::set<int> s[maxn];

inline int main() {
  read(n), read(m);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    s[a[i]].insert(i);
    auto iter = s[a[i]].upper_bound(i);
    int r = iter != s[a[i]].end() ? *iter : n + 1;
    iter = s[a[i]].lower_bound(i);
    int l = iter != s[a[i]].begin() ? *(--iter) : 0;
    int minn = std::min(r - i, i - l);
    int maxx = std::max(r - i, i - l);
    modify(1, 1, n, 1, minn, 1);
    modify(1, 1, n, maxx + 1, r - l, -1);
  }
  for (int i = 1; i <= m; ++i) {
    int opt;
    read(opt);
    switch (opt) {
      case 1: {
        int x, w, l, r;
        read(x), read(w);
        auto iter = s[a[x]].upper_bound(x);
        r = iter != s[a[x]].end() ? *iter : n + 1;
        iter = s[a[x]].lower_bound(x);
        l = iter != s[a[x]].begin() ? *(--iter) : 0;

        int minn = std::min(r - x, x - l);
        int maxx = std::max(r - x, x - l);
        modify(1, 1, n, 1, minn, -1);
        modify(1, 1, n, maxx + 1, r - l, 1);
        s[a[x]].erase(x);
        a[x] = w;
        s[w].insert(x);

        iter = s[w].upper_bound(x);
        r = iter != s[w].end() ? *iter : n + 1;
        iter = s[w].lower_bound(x);
        l = iter != s[w].begin() ? *(--iter) : 0;

        minn = std::min(r - x, x - l);
        maxx = std::max(r - x, x - l);
        modify(1, 1, n, 1, minn, 1);
        modify(1, 1, n, maxx + 1, r - l, -1);
      } break;
      case 2: {
        int k;
        read(k);
        cout << query(k) << '\n';
      } break;
    }
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("color.in", "r", stdin);
  freopen("color.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
